#include<iostream>
#include<unordered_map>
using namespace std;
class listnode {
public:
    int key;
    int val;
    listnode* next;
    listnode* prev;
    listnode(int key1 = 0, int val1 = 0) : key(key1), val(val1) {}
};
class LRUCache {
private:
    int capacity;
    unordered_map<int, listnode*> map;
    listnode* head;//哨兵节点
    void pop(listnode* node) {
        // 将这个节点从链表中进行删除，至于map删不删除，我这里不做处理
        listnode* prev = node->prev;
        listnode* next = node->next;
        prev->next = next;
        next->prev = prev;
    }
    void push_front(listnode* node) {
        // 将node节点头插入到链表中
        listnode* next = head->next;
        head->next = node;
        node->prev = head;
        next->prev = node;
        node->next = next;
    }
    void pop_back() {
        listnode* del = head->prev;        // 尾节点
        listnode* second_last = del->prev; // 倒数第二个节点
        second_last->next = head; // 更新倒数第二个节点的 next 指针
        head->prev = second_last; // 更新哨兵节点的前驱指针
        map.erase(del->key);      // 从哈希表中删除条目
        delete del;               // 释放内存
    }

public:
    LRUCache(int capacity) {
        head = new listnode();
        head->next = head;
        head->prev = head;
        this->capacity = capacity;
    }//创建哨兵节点，以及容量值
    int get(int key) {
        // 获取这个key的val，如果这个val不存在那么就返回-1，存在就获取，同时要将这个节点的位置进行头插
        if (map.find(key) != map.end()) {
            int ret = map[key]->val;
            pop(map[key]); // 首先要将这个节点从以前的位置进行删除
            push_front(map[key]); // 然后将这个节点值头插到链表中
            return ret;
        } else {
            return -1; // 不存在这个key
        }
    }

    void put(int key, int value) {
        if (map.find(key) != map.end()) {
            // 说明这个节点是存在的
            map[key]->val = value;
            pop(map[key]);
            push_front(map[key]);
            return;
        }
        // 说明这个节点是不存在的
        // 依旧是头插到链表中去
        listnode* node = new listnode(key, value);
        map[key] = node;
        push_front(node);
        if (map.size() > capacity) {
            // 储存的值大于了当前储存的上限，需要删除很久没有使用过的值
            pop_back();
        }
    }
};